package problemas;

import java.util.LinkedList;
import java.util.List;

import busca.BuscaAEstrela;
import busca.BuscaLargura;
import busca.BuscaProfundidade;
import busca.BuscaProfundidadeIterativa;
import busca.Estado;
import busca.Heuristica;
import busca.No;

public class Estado8Puzzle implements Estado, Heuristica{
    
    public static final short tam = 3;
    int[][] tabuleiro = new int[tam][tam];
    int colZero = -1;
    int linZero = -1;
    
    /* 1 2 3
       8   4        if goal state = 1
       7 6 5 */
    
    /*   1 2 
       3 4 5        if goal state = 2
       6 7 8 */
    int goalState = 1;
    
    /**
     *  estado inicial (aleatorio)
     */
    public Estado8Puzzle() {
        for (int r=0;r< (tam*tam);r++) {
            // tenta ata achar uma posicao livre
            int l = Math.round( (float)(Math.random()*(tam-1)) );
            int c = Math.round( (float)(Math.random()*(tam-1)) );
            while (tabuleiro[l][c] != 0) {
                l = Math.round( (float)(Math.random()*(tam-1)) );
                c = Math.round( (float)(Math.random()*(tam-1)) );
            }
            tabuleiro[l][c] = r;
        }
        setPosicaoBranco();
    }
    
    /**
     * cria um novo estado igual a outro
     */
    Estado8Puzzle(int[][] p) {
        for (int l=0;l<tam;l++) {
            for (int c=0;c<tam;c++) {
                tabuleiro[l][c] = p[l][c];
            }
            
        }
    }
    
    void setPosicaoBranco() {
        for (int l=0;l<tam;l++) {
            for (int c=0;c<tam;c++) {
                if (tabuleiro[l][c] == 0) {
                    colZero = c;
                    linZero = l;
                }
            }
        }
    }
    
    /**
     * ver se um estado e igual a outro
     */
    public boolean equals(Object o) {
    	if (o instanceof Estado8Puzzle) {
            Estado8Puzzle e = (Estado8Puzzle)o;
            for (int l=0;l<tam;l++) {
                for (int c=0;c<tam;c++) {
                    if (tabuleiro[l][c] != e.tabuleiro[l][c]) {
                        return false;
                    }
                }
            }
            return true;
        }
        return false;
    }
    
    public int hashCode() {
        return toString().hashCode();
    }

    /**
     * ver se o estado e meta
     */
    public boolean isGoal() {
        return this.equals(estadoMeta);
    }
    
    
    /**
     * Heuristica: calcula a quantidade de numeros fora do lugar
     */
    public int h() {
        return h1() + h2();
    }
    
    /**
     * Quantidade de numeros fora do lugar
     */
    public int h1() {
        int fora = 0;
        
        //VERIFICAÇÃO BASEADA NO ESTADO
        /* 1 2 3
           8   4        if goal state = 1
           7 6 5 */
        
        if (tabuleiro[0][0] != 1) fora++;
        if (tabuleiro[0][1] != 2) fora++;
        if (tabuleiro[0][2] != 3) fora++;
        if (tabuleiro[1][0] != 8) fora++;
        if (tabuleiro[1][1] != 0) fora++;
        if (tabuleiro[1][2] != 4) fora++;
        if (tabuleiro[2][0] != 7) fora++;
        if (tabuleiro[2][1] != 6) fora++;
        if (tabuleiro[2][2] != 5) fora++;
        
        return fora;
    }
    
    
    /**
     * Distancia do numero ao seu lugar original
     */
    public int h2() {
        int fora = 0;
        
        for (int n=0; n<(tam*tam); n++) {
            int l = getLineNumber(n);
            int c = getColumnNumber(n);
            int lMeta = estadoMeta.getLineNumber(n);
            int cMeta = estadoMeta.getColumnNumber(n);
            fora += Math.abs(l - lMeta);
            fora += Math.abs(c - cMeta);
        }
        return fora;
    }
    
    /** retorna a coluna de um numero */
    int getColumnNumber(int n) {
        for (int l=0;l<tam;l++) {
            for (int c=0;c<tam;c++) {
                if (tabuleiro[l][c] == n) {
                    return c;
                }
            }
        }
        return -1;
    }
    
    /** retorna a linha de um numero */
    int getLineNumber(int n) {
        for (int l=0;l<tam;l++) {
            for (int c=0;c<tam;c++) {
                if (tabuleiro[l][c] == n) {
                    return l;
                }
            }
        }
        return -1;
    }
    
    
    /**
     * retorna os sucessores
     */
    public List<Estado> sucessores() {
        List<Estado> suc = new LinkedList<Estado>(); // a lista de sucessores
        
        // pra cima
        if (linZero > 0) {
            Estado8Puzzle novo = new Estado8Puzzle(tabuleiro);
            novo.tabuleiro[linZero-1][colZero] = 0;
            novo.tabuleiro[linZero][colZero] = tabuleiro[linZero-1][colZero];
            novo.linZero = linZero-1;
            novo.colZero = colZero;
            suc.add(novo);
        }
        
        // pra baixo
        if (linZero < tam-1) {
            Estado8Puzzle novo = new Estado8Puzzle(tabuleiro);
            novo.tabuleiro[linZero+1][colZero] = 0;
            novo.tabuleiro[linZero][colZero] = tabuleiro[linZero+1][colZero];
            novo.linZero = linZero+1;
            novo.colZero = colZero;
            suc.add(novo);
        }
        
        // pra esq
        if (colZero > 0) {
            Estado8Puzzle novo = new Estado8Puzzle(tabuleiro);
            novo.tabuleiro[linZero][colZero-1] = 0;
            novo.tabuleiro[linZero][colZero] = tabuleiro[linZero][colZero-1];
            novo.linZero = linZero;
            novo.colZero = colZero-1;
            suc.add(novo);
        }
        
        // pra dir
        if (colZero < tam-1) {
            Estado8Puzzle novo = new Estado8Puzzle(tabuleiro);
            novo.tabuleiro[linZero][colZero+1] = 0;
            novo.tabuleiro[linZero][colZero] = tabuleiro[linZero][colZero+1];
            novo.linZero = linZero;
            novo.colZero = colZero+1;
            suc.add(novo);
        }
        
        return suc;
    }
    
    public List<Estado> antecessores() {
        return sucessores();
    }
    

    //verificacao da solução : http://www.8puzzle.com/8_puzzle_algorithm.html
    public boolean temSolucao() {
        Estado8Puzzle meta = estadoMeta;
        Estado8Puzzle t = new Estado8Puzzle(tabuleiro);
        
        int nroTrocas = 0;
        for (int l = 0; l < tam; l++) {
            for (int c = 0; c < tam; c++) {
            	nroTrocas += verifica(l,c,t.tabuleiro);
            }
        }
        
        boolean retorno = (nroTrocas % 2 == 0);
        //se retorno é true entao nrTrocas é par, senao é impar
        if(goalState == 1 && !retorno){
        	return true;
        }else if (goalState == 2 && retorno){
        	return true;
        }
        return false;
        
    }
    // verifica quantidade de itens menores do que ele que estao
    // apos a sua posicao
    public int verifica(int l, int c, int[][] tab){
    	int nrtrocas = 0;
    	int li = l;
    	int col = c;
    	for (int linha = li; linha < tam; linha++) {
             for (int coluna  = col; coluna < tam; coluna++) {
                 if(tab[linha][coluna] < tab[l][c] && tab[linha][coluna] != 0){
                	 nrtrocas++;
                 }
             }
            col = 0; 
         }
    	return nrtrocas;
    }
    
    private String toStringCache = null;
    
    public String toString() {
        if (toStringCache == null) {
            StringBuffer r = new StringBuffer("\n");
            for (int i=0;i<tam;i++) {
                for (int j=0;j<tam;j++) {
                    r.append(tabuleiro[i][j]);
                    if (j+1<tam) {
                        r.append(" ");
                    }
                }
                if (i+1<tam) {
                    r.append("\n");
                }
            }
            toStringCache = r + "\n";
        }
        return toStringCache;
    }
    
    
    /**
     * Custo para gerar um estado
     */
    public int custo() {
        return 1;
    }
    
    
    static public Estado8Puzzle getEstadoFacil() {
        Estado8Puzzle estadoFacil = new Estado8Puzzle(new int[][] {{8,1,3},{0,7,2},{6,5,4}});
        estadoFacil.setPosicaoBranco();
        return estadoFacil;
    }
    
    static public Estado8Puzzle getEstadoDificil() {
        Estado8Puzzle estadoDificil = new Estado8Puzzle(new int[][] {{7,8,6},{2,3,5},{1,4,0}} );
        estadoDificil.setPosicaoBranco();
        return estadoDificil;
    }
    
    static public Estado8Puzzle getEstadoMuitoDificil() {
        Estado8Puzzle estadoMuitoDificil = new Estado8Puzzle(new int[][] {{2,3,4},{1,0,5},{8,7,6}} );
        estadoMuitoDificil.setPosicaoBranco();
        return estadoMuitoDificil;
    }
    
    
    
    public static Estado8Puzzle getEstadoMeta() {
        return estadoMeta;
    }
    
    private final static Estado8Puzzle estadoMeta = setEstadoMeta();
    private static Estado8Puzzle setEstadoMeta() {
        Estado8Puzzle e8 = new Estado8Puzzle(new int[][] {{1,2,3},{8,0,4},{7,6,5}});
        //Estado8Puzzle e8 = new Estado8Puzzle(new int[][] {{0,1,2},{3,4,5},{6,7,8}});
        e8.setPosicaoBranco();
        return e8;
    }
    
    public static void main(String[] a) {
        //Estado8Puzzle state = getHardState();
    	Estado8Puzzle state = new Estado8Puzzle();
//    	Estado8Puzzle state = new Estado8Puzzle(new int[][] {{5,7,1},{8,3,6},{2,4,0}});
//    	state.setPosBranco();
    	
        //System.out.println("Estado inicial (h="+((Heuristica)state).h()+") ="+state);
    	System.out.println("Estado inicial:"+state);
        
        if (!state.temSolucao()) {
            System.out.println("Estado acima nao tem solucao!");
            return;
        }
        
        BuscaAEstrela buscaAEstrela = new BuscaAEstrela();
        No s1 = buscaAEstrela.busca(state);
        
        BuscaLargura buscaLargura = new BuscaLargura();
        No s2 = buscaLargura.busca(state);
        
        BuscaProfundidadeIterativa buscaProfundidadeIterativa = new BuscaProfundidadeIterativa();
        No s3 = buscaProfundidadeIterativa.busca(state);
        
        BuscaProfundidade buscaProfundidade = new BuscaProfundidade(25);
        No s4 = buscaProfundidade.busca(state);
        
        if (s1 != null) {
        	//System.out.println("**** ALGORITMO A ESTRELA *****");
        	//System.out.println("Solucao A estrela:" +s1.retornaCaminho());
            //System.out.println("Profundidade A estrela: "+s1.getProfundidade());
            //System.out.println("Tempo A estrela:"+ buscaAEstrela.getRunningTimeInSeconds()+"ms");
            //System.out.println("Nos Visitados:"+ buscaAEstrela.getNosVisitados()+"");
            //System.out.println("");
        	System.out.println(buscaAEstrela.getRunningTimeInSeconds());
        }else{
        	System.out.println("**** ALGORITMO A ESTRELA *****");
        	System.out.println("Tempo Esgotado");
        	System.out.println("");
        }
        if (s2 != null) {
        	//System.out.println("**** BUSCA LARGURA *****");
            //System.out.println("Solucao Busca Largura:" +s2.retornaCaminho());
            //System.out.println("Profundidade Busca Largura: "+s2.getProfundidade());
            //System.out.println("Tempo Busca Largura:"+ buscaLargura.getRunningTimeInSeconds()+"ms");
            //System.out.println("Nos Visitados:"+ buscaLargura.getNosVisitados());
            //System.out.println("");
        	System.out.println(buscaLargura.getRunningTimeInSeconds());
            
        }else{
        	System.out.println("**** BUSCA LARGURA  *****");
        	System.out.println("Tempo Esgotado");
        	System.out.println("");
        }
        if (s3 != null) {
        	//System.out.println("**** BUSCA PROFUNDIDADE ITERATIVA *****");
           // System.out.println("Solucao Busca Profundidade Iterativa:" +s3.retornaCaminho());
            //System.out.println("Profundidade Busca Profundidade Iterativa: "+s3.getProfundidade());
            //System.out.println("Tempo  Busca Profundidade Iterativa:"+ buscaProfundidadeIterativa.getRunningTimeInSeconds()+"ms");
            //System.out.println("Nos Visitados:"+ buscaProfundidadeIterativa.getNosVisitados());
            //System.out.println("");
        	System.out.println(buscaProfundidadeIterativa.getRunningTimeInSeconds());
            
        }else{
        	System.out.println("**** BUSCA PROFUNDIDADE ITERATIVA *****");
        	System.out.println("Tempo Esgotado");
        	System.out.println("");
        }
        if (s4 != null) {
        	//System.out.println("**** BUSCA PROFUNDIDADE *****");
            //System.out.println("Solucao Busca Profundidade:" +s4.retornaCaminho());
           // System.out.println("Profundidade Busca Profundidade: "+s4.getProfundidade());
            //System.out.println("Tempo  Busca Profundidade:"+ buscaProfundidade.getRunningTimeInSeconds()+"ms");
            //System.out.println("Nos Visitados:"+ buscaProfundidade.getNosVisitados());
            //System.out.println("");
        	System.out.println(buscaProfundidade.getRunningTimeInSeconds());
            
        }else{
        	System.out.println("**** BUSCA PROFUNDIDADE *****");
        	System.out.println("Tempo Esgotado");
        	System.out.println("");
        }
    }
}

